﻿//////////////////////////////////////////////////////////////////
//
// Roam.cs
//
// Copyright (c) 2012 Dan Pike.
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation files
// (the "Software"), to deal in the Software without restriction, 
// including without limitation the rights to use, copy, modify, merge, 
// publish, distribute, sublicense, and/or sell copies of the Software, 
// and to permit persons to whom the Software is furnished to do so, 
// subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included
// in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
// IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 
// TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
// SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
// This is part of an implementation of the algorithm described by
// Mark Duchaineau in his paper: "Realtime Optimal Adaptation for Planetary
// Geometry and Texture: 4-8 Tile Hierarchies" and in similar papers and
// example source code that he has published. Though I have studied it
// carefully and I believe that I understand how it works, all credit
// for the design of the algorithm must be directed to Mark Duchaineau.
//
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Utilities;

namespace Geometry
{
   public class Roam
   {
      ////////////////////////////////////////////////////////////////////////
      //
      public Roam()
      {
         free_ = new Stack<Diamond>(10000);
      }

      ////////////////////////////////////////////////////////////////////////
      //
      public bool initialize()
      {
         try
         {
            // Coarsest diamond mesh has a single complete "diamond" that fills the grid
            // (i.e. it is a diamond with a sloping diagonal from [0, 0] to [n, n]). The
            // parent and the grand-parent of this single diamond will also have centres
            // that lie within the grid, so that is the mesh that we need to create to
            // get going.
            // This leads naturally to a grid of vertices arranged 8 x 8 with the centre
            // of the "root" diamond at [3, 3], given logical coordinates that range 0-8
            Diamond[,] baseMesh = new Diamond[9, 9];

            int level;
            bool isParent = false;
            for (int j = 0; j < baseMesh.GetLength(1); ++j)
            {
               // Base-mesh diamonds exist only matching odd- or even- vertices.
               for (int i = j & 1; i < baseMesh.GetLength(0); i += 2)
               {
                  // The root diamond and its siblings are level 0. Parents of the root
                  // are level -1 and quad-ancestors are level -2
                  if (0 != (i & 1))
                  {
                     level = 0;
                  }
                  else
                  {
                     level = isParent ? -1 : -2;
                     isParent = !isParent;
                  }
                  
                  baseMesh[i, j] = Diamond.create(level, new Point3D((float)i, (float)j, 0.0f));
               }
            }
            root_ = baseMesh[3, 3];

            // Fix up the links
            bool slopingUp;
            for (int j = 0; j < baseMesh.GetLength(1); ++j)
            {
               // Base-mesh diamonds exist only matching odd- or even- vertices.
               for (int i = j & 1; i < baseMesh.GetLength(0); i += 2)
               {
                  Diamond diamond = baseMesh[i, j];
                  switch (diamond.level)
                  {
                     case 0 :
                        // Link to the parents whose location depends on whether the
                        // principal diagonal is sloping up or down
                        slopingUp = (0 == (i + j - 1) / 2);
                        diamond.p0 = baseMesh[i + 1, slopingUp ? j - 1 : j + 1];
                        diamond.p1 = baseMesh[i - 1, slopingUp ? j + 1 : j - 1];
                        diamond.a0 = baseMesh[slopingUp ? i - 1 : i + 1, j - 1];
                        diamond.a1 = baseMesh[slopingUp ? i + 1 : i - 1, j + 1];
                        break;

                     case -1:
                        if (baseMesh.GetLength(0) > i + 1)
                        {
                           if (0 < j)
                           {
                              diamond.k0 = baseMesh[i + 1, j - 1];
                           }
                           if (baseMesh.GetLength(1) > j + 1)
                           {
                              diamond.k1 = baseMesh[i + 1, j + 1];
                           }
                        }
                        if (0 < i)
                        {
                           if (baseMesh.GetLength(1) > j + 1)
                           {
                              diamond.k2 = baseMesh[i - 1, j + 1];
                           }
                           if (0 < j)
                           {
                              diamond.k0 = baseMesh[i - 1, j - 1];
                           }
                        }
                        // Mark it as split already, as it's a parent of the base mesh
                        diamond.split = true;
                        break;

                     case -2:
                        // Quad ancestors in the base mesh do not need to point
                        // anywhere, we only need to create them in order to
                        // give something for the root to point at

                        // Mark it as split already, as it's a parent of the base mesh
                        diamond.split = true;
                        break;

                     default:
                        throw new InvalidOperationException(string.Format("bad diamond level '{0}", diamond.level));
                  }
               }
            }

            return true;
         }
         catch (System.Exception ex)
         {
            logger_.exception(ex);
         }
         return false;
      }

      ////////////////////////////////////////////////////////////////////////
      //
      public void shutdown()
      {
      }

      ////////////////////////////////////////////////////////////////////////
      //
      public void update(DateTime timeLimit)
      {
      }

      ////////////////////////////////////////////////////////////////////////
      //
      private static Logger logger_ = new Logger();
      private Diamond root_;           // The root diamond exactly covers the source grid
      private Stack<Diamond> free_;    // Use a stack so we reuse diamonds quickly that will already be in cache before getting "staler" ones
   }
}
